#ifndef NETWORK_HPP
#define NETWORK_HPP

/*
	Network flow template.
	Modified from saffah's solution for
	ACM/ICPC World Finals 2013 C "Surely You Congest"
*/

#include "const.h"
#include <vector>
#include <cstring>

#define f(x, y, z) for(int x = (y); x <= (z); ++x)
#define g(x, y, z) for(int x = (y); x < (z); ++x)
#define INF 0x1f1f1f1f

namespace SDK
{

	class Network
	{
	public:
		static constexpr int MAX_NODES = MAP_SIZE * MAP_SIZE + 7;
		static constexpr int MAX_EDGES = MAX_NODES * MAX_NODES * 2 + 7;
		inline void init(int n){_init(n);}
		inline void addEdge(int s, int t, int w){_addEdge(s, t, w);}
		inline int sap(int s, int t){return _sap(s, t);}
		struct FlowEdge{
			int s, t, w;
		};
		inline std::vector<FlowEdge> flows(){return _flows();}
		int flow;
	private:
		inline void _init(int n){
			memset(this, 0, sizeof(Network));
			memset(head, 0x1f, sizeof(head));
			en = 0; v = n;
			f(i, 1, v) cs[i] = head[i];
		}
		inline int _sap(int ss, int tt){
			S = ss; T = tt;
			memset(id, 0x1f, sizeof(id));
			memset(gg, 0, sizeof(gg));
			f(i, 0, v) cs[i] = head[i];
			qh = qt = 0; que[0] = T; ++gg[id[T] = 0];
			while(qh <= qt){
				int s = que[qh];
				for(int c = head[s]; c != INF; c = next[c]) if(id[t[c]] == INF){
					++gg[id[t[c]] = id[s] + 1];
					que[++qt] = t[c];
				}
				qh++;
			}
			gg[0] = v + 1;
			flow = rn = 0; gap = -1;
			try{sap(S);}catch(fin){}
			return flow;
		}
		int head[MAX_NODES], id[MAX_NODES], en;
		int s[MAX_EDGES], t[MAX_EDGES], w[MAX_EDGES], next[MAX_EDGES], cs[MAX_NODES];
		int v, gap, S, T, rd[MAX_NODES], rn;
		int gg[MAX_NODES];
		int qh, qt, que[MAX_NODES];
		int maxans;
		struct fin{};
		inline bool sap(int d){
			if(d == T){
				int min = INF;
				g(i, 0, rn) if(w[rd[i]] < min) min = w[rd[i]], gap = s[rd[i]];
				g(i, 0, rn) w[rd[i]] -= min, w[rd[i] ^ 1] += min;
				flow += min; if(flow == maxans) throw(fin());
				--rn; return 1;
			}
			while(id[d] <= v + 1){
				while(cs[d] != INF){
					if(id[d] == id[t[cs[d]]] + 1 && w[cs[d]] > 0 && (rd[rn++] = cs[d], sap(t[cs[d]])) && d != gap) return --rn, 1;
					cs[d] = next[cs[d]];
				}
				int min = MAX_NODES - 5; cs[d] = head[d];
				while(cs[d] != INF){
					if(w[cs[d]] > 0 && id[t[cs[d]]] < min) min = id[t[cs[d]]];
					cs[d] = next[cs[d]];
				}
				--gg[id[d]];
				if(id[d] != min + 1 && !gg[id[d]]) throw(fin());
				++gg[id[d] = min + 1]; cs[d] = head[d];
				if(d != S) return --rn, 0;
			}
			--rn; return 0;
		}
		inline void _addEdge(int ccs, int ct, int cw){
			next[en] = head[ccs]; s[en] = ccs; t[en] = ct; w[en] = cw;
			head[ccs] = en; en++;
			next[en] = head[ct]; s[en] = ct; t[en] = ccs; w[en] = 0;
			head[ct] = en; en++;
		}
		inline std::vector<FlowEdge> _flows(){
			std::vector<FlowEdge> ans;
			for (int i = 1; i < en; i += 2) if (w[i])
			{
				FlowEdge fe;
				fe.s = t[i];
				fe.t = s[i];
				fe.w = w[i];
				ans.push_back(fe);
			}
			return ans;
		}
	};

}

#undef f
#undef g
#undef INF

#endif // NETWORK_HPP
